/**
 * @Author Fizz Pu
 * @Date 2020/11/15 下午10:40
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

/**
 * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
 *
 *  
 *
 * 示例：
 *
 * 输入：
 * matrix = [["1","0","1","0","0"],
 *           ["1","0","1","1","1"],
 *           ["1","1","1","1","1"],
 *           ["1","0","0","1","0"]]
 *
 * 输出：4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximal-square
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */


public class Lee221 {
    public int maximalSquare(char[][] matrix) {
        if(matrix == null) throw  new IllegalArgumentException();
        if(matrix.length == 0)return 0; // 记得空值检查

        int rowCount = matrix.length, colCount = matrix[0].length;
        int[][] dp = new int[rowCount][colCount];

        // 初始化
        for(int i = 0; i < colCount; ++i){
            dp[0][i] = matrix[0][i] - '0';
        }
        for(int j = 0; j < rowCount; ++j){
            dp[j][0] = matrix[j][0] - '0';
        }

        char curChar;
        int maxSize = 0;
        for(int i = 1; i < rowCount; ++i){
            for(int j = 1; j < colCount; ++j){
                curChar = matrix[i][j];
                if(curChar == '0')dp[i][j] = 0;
                else dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
                maxSize = Math.max(maxSize, dp[i][j]);
            }
        }

        return maxSize * maxSize;
    }
}
